package com.googlecode.gaal.suffix.impl;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.suffix.algorithm.api.ChildTableBuilder;
import com.googlecode.gaal.suffix.algorithm.api.LcpTableBuilder;
import com.googlecode.gaal.suffix.algorithm.api.SuffixTableBuilder;
import com.googlecode.gaal.suffix.api.EnhancedSuffixArray;
import com.googlecode.gaal.suffix.api.SuffixTree.Node;

public class EnhancedSuffixArrayBase extends AbstractIntervalTree<Node> implements EnhancedSuffixArray {

    protected final int[] childTable;
    protected final Node top;

    public EnhancedSuffixArrayBase(IntSequence sequence, int alphabetSize, int[] suffixTable, int[] lcpTable,
            int[] childTable) {
        super(sequence, alphabetSize, suffixTable, lcpTable);
        this.childTable = childTable;
        top = new NodeImpl(0, suffixTable.length - 1);
    }

    public EnhancedSuffixArrayBase(IntSequence sequence, int alphabetSize, SuffixTableBuilder suffixTableBuilder,
            LcpTableBuilder lcpTableBuilder, ChildTableBuilder childTableBuilder) {
        super(sequence, alphabetSize, suffixTableBuilder, lcpTableBuilder);
        this.childTable = childTableBuilder.buildChildTable(lcpTable);
        top = new NodeImpl(0, suffixTable.length - 1);
    }

    @Override
    public int[] getChildTable() {
        return childTable;
    }

    @Override
    public Node top() {
        return top;
    }

    @Override
    public Iterator<Node> preorderIterator() {
        return new PreorderIterator();
    }

    private class PreorderIterator implements Iterator<Node> {
        final Deque<Iterator<Node>> stack = new ArrayDeque<Iterator<Node>>();
        private Node next = top;

        {
            stack.push(top.childIterator());
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public Node next() {
            if (next == null)
                throw new NoSuchElementException();
            Node node = next;
            advance();
            return node;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private void advance() {
            Iterator<Node> childIterator = stack.peek();
            if (childIterator == null)
                next = null;
            else {
                if (childIterator.hasNext()) {
                    next = childIterator.next();
                    if (!next.isTerminal()) {
                        stack.push(next.childIterator());
                    }
                } else {
                    stack.pop();
                    advance();
                }
            }
        }
    }

    private class ChildIterator implements Iterator<Node> {
        private final int right;
        private int next;
        private Node node;

        private ChildIterator(Node parent) {
            int left = parent.left();
            right = parent.right();
            if (left == right) {
                node = null;
            } else {
                // left < childTable[right] && childTable[right] <= right
                if (childTable[left] <= right) { // is last
                    next = childTable[left];
                } else {
                    next = childTable[right];
                }
                node = new NodeImpl(left, next - 1);
            }
        }

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public Node next() {
            if (node == null)
                throw new NoSuchElementException();
            Node result = node;
            advance();
            return result;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private void advance() {
            if (next == -1) {
                node = null;
            } else if (next < right && !isLast(next)) {
                int left = next;
                next = childTable[next];
                node = new NodeImpl(left, next - 1);
            } else {
                node = new NodeImpl(next, right);
                next = -1;
            }
        }

        private boolean isLast(int left) {
            return lcpTable[left] != lcpTable[childTable[left]];
        }

    }

    protected class NodeImpl extends AbstractInterval implements Node {

        protected NodeImpl(int left, int right) {
            super(left, right);
        }

        @Override
        public int lcp() {
            if (left == right)
                return -1;
            int mid = childTable[right];
            if (left < mid && mid <= right) {
                return lcpTable[mid];
            } else {
                return lcpTable[childTable[left]];
            }
        }

        @Override
        public Iterator<Node> childIterator() {
            return new ChildIterator(this);
        }
    }
}